package com.promote.algorithm;

/**
 * @ClassName RemoveNthFromEnd
 * Description 删除链表的倒数第n个节点
 * @Author LiZiHao
 * Date 2022/3/16 11:46
 * @Version 1.0
 **/
public class RemoveNthFromEnd {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 先求出链表的长度length，然后就可以找到要删除链表的前一个结点，让他的前一个结点指向要删除结点的下一个结点即可
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd1(ListNode head, int n) {

        ListNode pre = head;
        int last = length(head) - n;

        //如果last等于0表示删除的是头结点
        if (last == 0) {
            return head.next;
        }

        //首先找到要删除节点的前一个节点
        for (int i = 0; i < last - 1; i++) {
            pre = pre.next;
        }

        //让前一个节点的next指向要删除节点的next
        pre.next = pre.next.next;
        return head;
    }

    private int length(ListNode node) {
        int res = 0;

        while (node != null) {
            res++;
            node = node.next;
        }
        return res;
    }

    /**
     * 双指针求解
     * 我们可以使用两个指针，一个指针fast先走n步，然后另一个指针slow从头结点开始，找到要删除结点的前一个结点，这样就可以完成结点的删除了。
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode fast = head;
        ListNode slow = head;

        //fast移动n步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        //如果fast为空，表示删除的是头结点
        if (fast == null) {
            return head.next;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }

    /**
     * 递归解决
     * 算链表长度的递归其实可以把它看做是从后往前计算，当计算的长度是n的时候就表示遍历到了倒数第n个节点了，这里只要求出倒数第n+1个节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd3(ListNode head, int n) {
        int pos = lengthB(head, n);

        if (pos == n) {
            return head.next;
        }
        return head;
    }

    private int lengthB(ListNode node, int n) {
        if (node == null) {
            return 0;
        }
        int pos = lengthB(node.next,n) +1;
        if (pos == n + 1) {
            node.next = node.next.next;
        }
        return pos;
    }
}
